package day04

// day04
//
// 51. N 皇后
//
// https://leetcode.cn/problems/n-queens/
//
// ```go
func solveNQueens(n int) [][]string {
	result := make([][][]int, 0)
	var dfs func(path [][]int, row int)
	dfs = func(path [][]int, row int) {
		if row == n {
			tmp := make([][]int, len(path))
			for i := 0; i < n; i++ {
				tmp[i] = make([]int, n)
				copy(tmp[i], path[i])
			}
			result = append(result, tmp)
		}
		for i := 0; i < n; i++ {
			if check(row, i, path, n) {
				path[row][i] = 1
				dfs(path, row+1)
				path[row][i] = 0
			}
		}
	}
	path := make([][]int, n)
	for i := 0; i < n; i++ {
		path[i] = make([]int, n)
	}
	dfs(path, 0)
	ans := make([][]string, len(result))
	for idx, cur := range result {
		ans[idx] = make([]string, n)
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if cur[i][j] == 1 {
					ans[idx][i] += "Q"
				} else {
					ans[idx][i] += "."
				}
			}
		}
	}
	return ans
}

func check(row, col int, path [][]int, n int) bool {
	//行
	for i := 0; i < n; i++ {
		if path[i][col] == 1 {
			return false
		}
	}
	//45
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if path[i][j] == 1 {
			return false
		}
	}
	//135
	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if path[i][j] == 1 {
			return false
		}
	}
	return true
}

//```

// 37. 解数独
//
// https://leetcode.cn/problems/sudoku-solver/
//
// ```go
func solveSudoku(board [][]byte) {
	n := len(board)
	var dfs func() bool
	dfs = func() bool {
		for row := 0; row < n; row++ {
			for col := 0; col < n; col++ {
				if board[row][col] != '.' {
					continue
				}
				for i := '1'; i <= '9'; i++ {
					if check(row, col, board, byte(i)) {
						board[row][col] = byte(i)
						if dfs() {
							return true
						}
						board[row][col] = '.'
					}
				}
				return false
			}
		}
		return true
	}
	dfs()
}

func check(row, col int, board [][]byte, num byte) bool {
	//行 列
	for i := 0; i < len(board); i++ {
		if board[i][col] == num {
			return false
		}
		if board[row][i] == num {
			return false
		}
	}
	//3 * 3
	i, j := (row/3)*3, (col/3)*3
	for startRow := i; startRow < i+3; startRow++ {
		for startCol := j; startCol < j+3; startCol++ {
			if board[startRow][startCol] == num {
				return false
			}
		}
	}
	return true
}

//```
